/**
 * https://leetcode.cn/submissions/detail/582427732/
 * 695. 岛屿的最大面积
 * Medium, 黄伟杰 2024.11.22
 * 并查集
 */

class union_find
{
private:
    vector<int> parent;
    vector<int> rank;

public:
    int maxx = 0;
    // 构造从 0 到 n - 1 的节点
    union_find(int n)
    {
        parent.resize(n);
        rank.resize(n);
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    // 找到根节点
    int find(int index)
    { // 递归函数，找根节点的同时进行路径压缩
        while (index != parent[index])
        {
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (rank[x] > rank[y])
        {
            parent[y] = x;
            rank[x] += rank[y];
        }
        else
        {
            parent[x] = y;
            rank[y] += rank[x];
        }
        maxx = max(maxx, max(rank[x], rank[y]));
    }
};
class Solution
{
    const int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // 四个方向
public:
    int maxAreaOfIsland(vector<vector<int>> &grid)
    {
        int n = grid.size();
        int m = grid[0].size();
        union_find *uf = new union_find(n * m);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == 1)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        int x = i + dir[k][0];
                        int y = j + dir[k][1];
                        if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1)
                        {
                            uf->unite(i * m + j, x * m + y); // 两个格子联通}
                        }
                    }
                    uf->maxx = max(1, uf->maxx);
                }
            }
        }
        return uf->maxx;
    }
};